package com.itheima.leetcode.od.b.stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
 * <h3>删除重复数字后的最大数字</h3>
 * 给定一个由纯数字组成以字符串表示的数值，现要求字符串中的每个数字最多只能出现2次，超过的需要进行删除；
 * <p>
 * 删除某个重复的数字后，其它数字相对位置保持不变。
 * <p>
 * 如”34533″，数字3重复超过2次，需要删除其中一个3，删除第一个3后获得最大数值”4533″
 * <p>
 * 请返回经过删除操作后的最大的数值，以字符串表示。
 * <p>
 * 输入描述
 * <p>
 * 第一行为一个纯数字组成的字符串，长度范围：[1,100000]
 * <p>
 * 输出描述
 * <p>
 * 输出经过删除操作后的最大的数值
 * <p>
 * 示例1
 * <p>
 * 输入:
 * <p>
 * 34533
 * <p>
 * 输出:
 * 4533
 * <p>
 * 示例2
 * <p>
 * 输入:
 * <p>
 * 5445795045
 * <p>
 * 输出:
 * <p>
 * 5479504
 */
public class LargestNumberAfterRemovingDuplicates {
    public static void main(String[] args) {
        /*// 输入处理
        Scanner in = new Scanner(System.in);
        String string1 = in.nextLine();

        int[] nums = new int[string1.length()];
        for (int i = 0; i < string1.length(); i++) {
            nums[i] = string1.charAt(i) - 48;
        }*/

        String string1 = "34533";
        int[] nums = Arrays.stream(string1.split("")).mapToInt(Integer::parseInt).toArray();

        System.out.println(get_max_number(nums));
    }

    /**
     * 字符串去重后个数
     *
     * @param nums
     * @return
     */
    public static String get_max_number(int[] nums) {
        // 统计出现次数 + 已经使用的次数
        HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> st_cnt = new HashMap<Integer, Integer>();

        for (int v : nums) {
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }

        // 栈
        LinkedList<Integer> stack = new LinkedList<>();
        for (int x : nums) {

            cnt.put(x, cnt.get(x) - 1);

            // 已经使用2次，直接跳过
            if (st_cnt.containsKey(x) && st_cnt.get(x) == 2) {
                continue;
            }

            // 当前数字大于栈尾数字，且栈尾数字出现超过2次
            while (!stack.isEmpty() && x > stack.peek()) {
                if (cnt.containsKey(stack.peek()) && cnt.get(stack.peek()) < 2) {
                    break;
                }

//                cnt.put(stack.peek(), cnt.get(stack.peek()) - 1); // 我觉得这里写错了 cnt应该是存剩余的元素计数
                st_cnt.put(stack.peek(), st_cnt.get(stack.peek()) - 1);
                stack.pop();
            }

            stack.add(x);
            st_cnt.put(x, st_cnt.getOrDefault(x, 0) + 1);
        }

        return stack.stream().map(String::valueOf).collect(Collectors.joining(""));
    }
}